Techniques for transmission of files between a sender and a recipient over a communications channel are the subject of much literature. Preferably, a recipient desires to receive an exact copy of data transmitted over a channel by a sender with some level of certainty. Where the channel does not have perfect fidelity (which covers most all physically realizable systems), one concern is how to deal with data lost or garbled in transmission. Lost data (erasures) are often easier to deal with than corrupted data (errors) because the recipient cannot always tell when corrupted data is data received in error. Many error-correcting codes have been developed to correct for erasures and/or for errors. Typically, the particular code used is chosen based on some information about the infidelities of the channel through which the data is being transmitted and the nature of the data being transmitted. For example, where the channel is known to have long periods of infidelity, a burst error code might be best suited for that application. Where only short, infrequent errors are expected a simple parity code might be best.
As used herein, “source data” refers to data that is available at one or more senders and that a receiver is used to obtain, by recovery from a transmitted sequence with or without errors and/or erasures, etc. As used herein, “encoded data” refers to data that is conveyed and can be used to recover or obtain the source data. In a simple case, the encoded data is a copy of the source data, but if the received encoded data differs (due to errors and/or erasures) from the transmitted encoded data, in this simple case the source data might not be entirely recoverable absent additional data about the source data. Transmission can be through space or time. In a more complex case, the encoded data is generated based on source data in a transformation and is transmitted from one or more senders to receivers. The encoding is said to be “systematic” if the source data is found to be part of the encoded data. In a simple example of systematic encoding, redundant information about the source data is appended to the end of the source data to form the encoded data.
Also as used herein, “input data” refers to data that is present at an input of an FEC (forward-error correcting) encoder apparatus or an FEC encoder module, component, step, etc., (“FEC encoder”) and “output data” refers to data that is present at an output of an FEC encoder. Correspondingly, output data would be expected to be present at an input of an FEC decoder and the FEC decoder would be expected to output the input data, or a correspondence thereof, based on the output data it processed. In some cases, the input data is, or includes, the source data, and in some cases, the output data is, or includes, the encoded data. For example, the input data would be the source data if there is no processing before the input of an FEC encoder. However, in some cases, the source data is processed into a different form (e.g., a static encoder, an inverse encoder or another process) to generate intermediate data that is presented to the FEC encoder instead of the source data.
In some cases, a sender device or sender program code may comprise more than one FEC encoder, i.e., source data is transformed into encoded data in a series of a plurality of FEC encoders. Similarly at the receiver, there may be more than one FEC decoder applied to generate source data from received encoded data.
Data can be thought of as partitioned into symbols. An encoder is a computer system, device, electronic circuit, or the like, that generates encoded symbols or output symbols from a sequence of source symbols or input symbols and a decoder is the counterpart that recovers a sequence of source symbols or input symbols from received or recovered encoded symbols or output symbols. The encoder and decoder are separated in time and/or space by the channel and any received encoded symbols might not be exactly the same as corresponding transmitted encoded symbols and they might not be received in exactly the same sequence as they were transmitted. The “size” of a symbol can be measured in bits, whether or not the symbol is actually broken into a bit stream, where a symbol has a size of M bits when the symbol is selected from an alphabet of 2M symbols. In many of the examples herein, symbols are measured in octets and codes might be over a field of 256 possibilities (there are 256 possible 8-bit patterns within each octet), but it should be understood that different units of data measurement can be used and it is well-known to measure data in various ways. In the general literature, the term “byte” is sometimes used interchangeably with the term “octet” to indicate an 8-bit value, although in some contexts “byte” indicates an X-bit value where X is not equal to 8, e.g., X=7, and thus, in general, the term “octet” is used herein. Unless otherwise indicated, the examples herein are not limited to a particular integer or noninteger number of bits per symbol.
Luby I describes the use of codes, such as chain reaction codes, to address error correction in a compute-efficient, memory-efficient and bandwidth-efficient manner. One property of the encoded symbols produced by a chain reaction encoder is that a receiver is able to recover the original file as soon as enough encoded symbols have been received. Specifically, to recover the original K source symbols with a high probability, the receiver needs approximately K+A encoded symbols.
The “absolute reception overhead” for a given situation is represented by the value A, while a “relative reception overhead” can be calculated as the ratio A/K. The absolute reception overhead is a measure of how much extra data needs to be received beyond the information theoretic minimal amount of data, and it may depend on the reliability of the decoder and may vary as a function of the number, K, of source symbols. Similarly, the relative reception overhead, A/K, is a measure of how much extra data needs to be received beyond the information theoretic minimal amount of data relative to the size of the source data being recovered, and also may depend on the reliability of the decoder and may vary as a function of the number K of source symbols.
Chain reaction codes are extremely useful for communication over a packet based network. However, they can be fairly computationally intensive at times. A decoder might be able to decode more often, or more easily, if the source symbols are encoded using a static encoder prior to a dynamic encoder that encodes using a chain reaction or another rateless code. Such decoders are shown in Shokrollahi I, for example. In examples shown there, source symbols are input symbols to a static encoder that produces output symbols that are input symbols to a dynamic encoder that produces output symbols that are the encoded symbols, wherein the dynamic encoder is a rateless encoder that that can generate a number of output symbols in a quantity that is not a fixed rate relative to the number of input symbols. The static encoder might include more than one fixed rate encoder. For example a static encoder might include a Hamming encoder, a low-density parity-check (“LDPC”) encoder, a high-density parity-check (“HDPC”) encoder, and/or the like.
Chain reaction codes have a property that as some symbols are recovered at the decoder from the received symbols, those symbols might be able to be used to recover additional symbols, which in turn might be used to recover yet more symbols. Preferably, the chain reaction of symbol solving at the decoder can continue such that all of the desired symbols are recovered before the pool of received symbols is used up. Preferably, the computational complexity of performing chain reaction encoding and decoding processes is low.
A recovery process at the decoder might involve determining which symbols were received, creating a matrix that would map the original input symbols to those encoded symbols that were received, then inverting the matrix and performing a matrix multiplication of the inverted matrix and a vector of the received encoded symbols. In a typical system, a brute force implementation of this can consume excessive computing effort and memory requirements. Of course, for a particular set of received encoded symbols, it might be impossible to recover all of the original input symbols, but even where it is possible, it might be very computationally expensive to compute the result.
Forward Error Correction (“FEC”) Object Transmission Information (“OTI”), or “FEC OTI”
Based on the FEC OTI a receiver receives (or is able to infer), the receiver can determine the source block and sub-block structure of the file transfer. In [Raptor-RFC-5053] and [RaptorQ-Spec], the FEC Payload ID is (SBN, ESI), where in [Raptor-RFC-5053] the source block number (SBN) is 16 bits and the encoding symbol ID (ESI) is 16 bits, whereas in [RaptorQ-Spec] the SBN is 8 bits and the ESI is 24 bits, as illustrated in FIG. 1 herein. One disadvantage of this FEC Payload ID format is that one has to pre-determine the number of bits of the FEC Payload ID to allocate to the SBN and to the ESI, and it is sometimes difficult to determine a proper mix that will be adequate for all file delivery parameters.
For example, when using [Raptor-RFC-5053], having only 216=65,536 ESIs available might be limiting in some situations, since in some cases there might be a source block with 8,192 source symbols and thus the number of encoded symbols is only a factor of 8 larger, limiting the possible code rate that could be used to be limited to not go down below ⅛ in this case. In this example, it may be that 216=65,536 source blocks available could be more than would ever be used, e.g., with 8,192 source symbols of 1,024 octets each, the size of the file that could be supported is 524 GB, which in many applications is two orders of magnitude larger than is needed.
As another example, when using [RaptorQ-Spec], having only 28=256 SBNs available might be limiting in some situations, since for a 4 GB file, if each source block is limited to 8 MB (which might be the case if the maximum sub-block size is 256 KB, the minimum sub-symbol size is 32 octets, and the symbol size is 1,024 octets) then limiting the number of source blocks to 256 in turn limits the file size to 2 GB. In this example, it may be that having available 224=16,777,216 possible encoded symbols are more than would ever be used, e.g., with 8,192 source symbols the number of possible encoded symbols is 2,048 times larger, which may never be needed in some applications.
Another desirable property is to provide capabilities for prioritized encoding transmission, sometimes also called unequal error protection (“UEP”), between different parts of the file. For example, it might be desirable to protect the first 10% of the file more strongly against packet loss than the remaining 90%. For example, [LDPC-Extensions] describes how [LDPC-RFC-5170] can be extended to provide support for UEP. In this case, the actual FEC code itself is modified to provide different levels of parity protection on different parts of a file. However, there are drawbacks to this approach. For example, it is not desirable to have to modify the FEC code itself to provide UEP, as this complicates implementing and testing the FEC code itself. Furthermore, as the results shown in FIG. 6 of [LDPC-Extensions], the resulting performance of such an approach in terms of the resiliency to packet loss that is provided for the different parts of the file is far from optimal.
One way to provide UEP file delivery capabilities, as described in [PET] and [PET-Patent], is to allocate different parts of each packet for the different parts of the file according to their priority and size. However, a concern is how to incorporate such UEP methods in such a way that each different part of the file can be partitioned into source blocks and sub-blocks independently of other parts of the file, for example to support small memory decoding of each part of the file, and yet at the same time provide an FEC Payload ID within each packet that allows the receiver to determine which symbol for each part of the file is contained in each packet. This is very difficult to support using an FEC Payload ID of the format (SBN, ESI), as for each part of the file the corresponding SBN and ESI for the symbol in the packet for a first part of the file might be different than the SBN and ESI for the symbol in the packet for a second part of the file.
HTTP Repair Methods
The way that repair requests are made in the 3GPP MBMS standard TS 26.346 for broadcast/multicast file delivery, for example, is to use the FEC Payload ID specified in [Raptor-RFC-5053], i.e., by specifying the source block number (SBN) and the encoding symbol identifier (ESI). Although this method is reasonable if the servers that respond to repair requests have specialized methods that require them to determine the file delivery structure used in the broadcast/multicast file delivery, i.e., they are required to interpret which parts of the file are referenced by the requested SBNs and ESIs, which requires knowing the source block and sub-block structure as well as the symbol size, T. On the other hand, there may be millions of broadcast/multicast receivers spread across a large geographic area, and requiring deployment of specialized response servers is both expensive and cumbersome, both from a capital expense and from an operational perspective. What are widely deployed are standard HTTP web servers and web caches that support Internet delivery, e.g., web pages, video streaming, etc. What is desirable is a method that supports using standard HTTP web servers and web caches as broadcast/multicast response servers.